from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def solve(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        size = len(nums)

        cache_range = {}
        for x, y in queries:
            num = (size - 1 - x) // y
            last = x + num * y
            if (last, y) not in cache_range or cache_range[(last, y)] < num + 1:
                cache_range[(last, y)] = num + 1

        cache = {}
        for last, y in cache_range:
            cache[(last, y)] = [0]
            for i in range(cache_range[(last, y)]):
                cache[(last, y)].append(cache[(last, y)][-1] + nums[last - y * i])

        ans = []
        for x, y in queries:
            num = (size - 1 - x) // y
            last = x + num * y
            ans.append(cache[(last, y)][num + 1] % MOD)
        return ans


if __name__ == "__main__":
    print(Solution().solve(nums=[0, 1, 2, 3, 4, 5, 6, 7], queries=[[0, 3], [5, 1], [4, 2]]))  # [9,18,10]
    print(Solution().solve(nums=[100, 200, 101, 201, 102, 202, 103, 203], queries=[[0, 7]]))  # [303]

    # 测试用例3/26
    # [34771484, 502200359, 382180183, 314334592, 476212784, 476212784, 775202637, 541051933, 745111839, 689321821, 386290837, 709290903, 809996292, 421653356, 896058469, 314334592, 43839402, 476212784, 929860496, 494081947, 670503948, 960700706, 275232737, 329868152, 60676136, 33563353, 93718862, 200504064, 314334592, 1114799, 152261702, 203941574, 768606672, 278715698, 303171493, 362355685, 101810083, 980385976, 768606672, 524233877, 79169511, 849313493, 161434840, 196086727, 132121098, 625463281, 768606672, 849313493, 744376400, 861054789, 987178468, 457704047, 146682864, 856856616, 575568229, 224759294, 303171493, 582330342, 476212784, 314334592, 893152895, 739362334, 325614701, 121855649, 275232737, 836697235, 611336708, 931931936, 106375949, 806862779, 171156108, 12368668, 753303382, 152484979, 913709891, 303171493, 335525681, 716968085]
    print(Solution().solve(
        nums=[112844299, 103519373, 865975544, 681648004, 859788916, 524257634, 721810308, 488134798, 262541753,
              899571207, 343647455, 565324023, 64743988, 317945005, 41441783, 896446773, 811182810, 493579217,
              295096668, 441940346, 572339870, 428843370, 946810157, 533039266, 240755301, 48021093, 970755669,
              809996292, 707948659, 670503948, 856856616, 490866470, 11741296, 929860496, 392758771, 303171493,
              34771484, 325614701, 913709891, 314334592, 849313493, 60676136, 768606672, 476212784, 275232737],
        queries=[[36, 9], [20, 13], [28, 1], [39, 7], [43, 2], [43, 20], [2, 5], [13, 2], [19, 16], [14, 2], [37, 4],
                 [8, 15], [27, 20], [20, 20], [5, 14], [39, 10], [42, 2], [43, 5], [33, 16], [7, 2], [29, 18], [3, 6],
                 [44, 18], [18, 18], [41, 10], [28, 9], [35, 4], [10, 20], [39, 18], [3, 4], [10, 3], [16, 18],
                 [42, 18], [5, 16], [35, 11], [25, 14], [24, 8], [21, 10], [42, 16], [25, 18], [8, 17], [40, 6],
                 [4, 19], [18, 6], [26, 8], [30, 12], [42, 4], [40, 9], [39, 1], [32, 8], [14, 15], [30, 7], [1, 14],
                 [30, 15], [15, 3], [17, 12], [35, 11], [6, 16], [43, 6], [39, 11], [40, 2], [26, 16], [37, 14],
                 [8, 12], [44, 8], [18, 2], [1, 1], [30, 4], [11, 2], [38, 2], [5, 9], [7, 18], [15, 15], [35, 5],
                 [38, 17], [35, 18], [19, 5], [24, 19]]))
